package com.tys.algorithm.advanced.test.class15;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;

/**
 * 本题为leetcode原题：付费
 * 测试链接：https://leetcode.com/problems/number-of-islands-ii/
 * <p>
 * 一个由 m 行和 n 列组成的2d 网格地图最初是用水填充的。
 * 我们可以执行一个附加操作，将位置(行，列)的水变成陆地。
 * 给定一个操作位置的列表，计算每次附加操作后的岛屿数量。
 * 岛屿被水环绕，由水平或垂直连接相邻的陆地而形成。
 * 你可以假设网格的四个边都被水包围着。
 * 例如：
 * 3*3的矩阵，开始都是0水，1是陆地
 * [0,0]设置为1，是1个岛
 * [0,1]设置为1，是1个岛
 * [1,2]设置为1，是2个岛
 * [2,1]设置为1，是3个岛
 * 每设置一个位置，就更新岛的数量
 */
public class Code03_NumberOfIslandsII {
    //方法1：
    public static List<Integer> numIslands21(int m, int n, int[][] positions) {
        UnionFind1 uf = new UnionFind1(m, n);
        List<Integer> ans = new ArrayList<>();
        for (int[] position : positions) {
            //每次连完放ans
            ans.add(uf.connect(position[0], position[1]));
        }
        return ans;
    }

    public static class UnionFind1 {
        private int[] parent; //父
        /**
         * size[i]=1, 合并后，i挂j下，size[j]修改，size[i]=1不动
         * size[i]=0表示 i 未被初始化
         * size[i]=1表示 i 被初始化过
         */
        private int[] size;//大小
        private int[] help;
        private final int row; //行
        private final int col; //列
        private int sets; //岛数

        public UnionFind1(int m, int n) {
            row = m;
            col = n;
            sets = 0;
            int len = row * col;
            parent = new int[len];
            size = new int[len];
            help = new int[len];
        }

        //计算索引
        private int index(int r, int c) {
            return r * col + c;
        }

        //找代表节点
        private int find(int i) {
            int hi = 0;
            while (i != parent[i]) {
                help[hi++] = i;
                i = parent[i];
            }
            for (hi--; hi >= 0; hi--) {
                parent[help[hi]] = i;
            }
            return i;
        }

        //合并
        private void union(int r1, int c1, int r2, int c2) {
            //越界返回
            if (r1 < 0 || r1 == row || r2 < 0 || r2 == row || c1 < 0 || c1 == col || c2 < 0 || c2 == col) {
                return;
            }
            //得到索引1
            int i1 = index(r1, c1);
            //得到索引2
            int i2 = index(r2, c2);
            //只要有一个不为1就返回：相邻的1才合并
            if (size[i1] == 0 || size[i2] == 0) {
                return;
            }
            //找到父1
            int f1 = find(i1);
            //找到父2
            int f2 = find(i2);
            if (f1 != f2) { //不相同
                //判断大小，小挂大
                if (size[f1] >= size[f2]) {
                    //f1大
                    size[f1] += size[f2];
                    //f2挂f1
                    parent[f2] = f1;
                } else {
                    //f2大
                    size[f2] += size[f1];
                    //f1挂f2
                    parent[f1] = f2;
                }
                sets--;
            }
        }

        //r行,c列，变1
        public int connect(int r, int c) {
            //计算索引
            int index = index(r, c);
            if (size[index] == 0) { //没有空降过，没初始化过
                parent[index] = index; //自己指自己
                size[index] = 1; //自己的大小设置为1
                sets++; //集合加1
                //自己与上合并
                union(r - 1, c, r, c);
                //自己与下合并
                union(r + 1, c, r, c);
                //自己与左合并
                union(r, c - 1, r, c);
                //自己与右合并
                union(r, c + 1, r, c);
            }
            //返回集合数
            return sets;
        }

    }

    // 课上讲的如果m*n比较大，会经历很重的初始化，而k比较小
    // 怎么优化的方法
    public static List<Integer> numIslands22(int m, int n, int[][] positions) {
        UnionFind2 uf = new UnionFind2();
        List<Integer> ans = new ArrayList<>();
        for (int[] position : positions) {
            ans.add(uf.connect(position[0], position[1]));
        }
        return ans;
    }

    public static class UnionFind2 {
        private HashMap<String, String> parent;
        private HashMap<String, Integer> size;
        private ArrayList<String> help;
        private int sets;

        public UnionFind2() {
            parent = new HashMap<>();
            size = new HashMap<>();
            help = new ArrayList<>();
            sets = 0;
        }

        private String find(String cur) {
            while (!cur.equals(parent.get(cur))) {
                help.add(cur);
                cur = parent.get(cur);
            }
            for (String str : help) {
                parent.put(str, cur);
            }
            help.clear();
            return cur;
        }

        private void union(String s1, String s2) {
            //不存在就返回
            if (parent.containsKey(s1) && parent.containsKey(s2)) {
                String f1 = find(s1);
                String f2 = find(s2);
                if (!f1.equals(f2)) {
                    int size1 = size.get(f1);
                    int size2 = size.get(f2);
                    String big = size1 >= size2 ? f1 : f2;
                    String small = big == f1 ? f2 : f1;
                    parent.put(small, big);
                    size.put(big, size1 + size2);
                    sets--;
                }
            }
        }

        public int connect(int r, int c) {
            //转成字符串
            String key = String.valueOf(r) + "_" + String.valueOf(c);
            if (!parent.containsKey(key)) { //没有来过
                parent.put(key, key); //自己指自己
                size.put(key, 1); //自己大小1
                sets++;//集合加1
                //上
                String up = String.valueOf(r - 1) + "_" + String.valueOf(c);
                //下
                String down = String.valueOf(r + 1) + "_" + String.valueOf(c);
                //左
                String left = String.valueOf(r) + "_" + String.valueOf(c - 1);
                //右
                String right = String.valueOf(r) + "_" + String.valueOf(c + 1);
                //合并上
                union(up, key);
                //合并下
                union(down, key);
                //合并左
                union(left, key);
                //合并右
                union(right, key);
            }
            return sets;
        }

    }

}
